package com.togo.algorithm.medium.design;

import java.util.LinkedList;

/**
 * @Author taiyn
 * @Description TODO
 * @Date 上午11:55 2022/5/8
 **/
public class qqq {

    private char[][] grid;
    private int x;
    private int y;
    public boolean hasValidPath(char[][] grid) {

        if(grid == null || grid[0] == null || grid[0][0] != '(') return false;

        this.grid = grid;
        this.x = grid.length - 1;
        this.y = grid[0].length - 1;

        return cur(new LinkedList<Character>(), 0, 0);
    }

    private boolean cur(LinkedList<Character> stack, int i, int j) {

        if(i > x || j > y) return false;

        if(grid[i][j] == '(') {
            stack.addFirst(grid[i][j]);
        } else {
            if(stack.size() == 0) {
                return false;
            }

            if(stack.getFirst() == '(') {
                stack.poll();
            } else {
                stack.addFirst(grid[i][j]);
                return false;
            }
        }

        boolean r = cur(stack, i + 1, j);
        if(!r) {
            stack.poll();
        }
        boolean d = cur(stack, i, j + 1);
        if(!d) {
            stack.poll();
        }

        return r || d;
    }

    public static void main(String[] args) {

        qqq s = new qqq();

        char[][] grid = new char[][]{{'(','(','('}, {')','(',')'},{'(','(',')'},{'(','(',')'}};
        s.hasValidPath(grid);
    }
}
